# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/15 上午10:18
    Author  : Thinkgamer
    File    : 763-划分字母区间.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/partition-labels/
"""

"""
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]

解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。


提示：
S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。
"""

"""
	v1 思路：首先统计每个字符出现的次数，然后从第一个字符开始遍历
	因为一个字符只能出现在一个序列中，所以第一个字符必须全部包含在第一个序列中，然后第一个序列中涉及的字符也必须全部在第一个序列中
	
	第一个序列遍历结束时，置空临时遍历
	
	v2 思路：首先统计每个字符第一次和最后一次出现的下标
		然后从第一个字符开始遍历，最后的一个下标进行赋值，以此判断当前遍历的点是否在最大下标的范围内，不在的话，更新最大下标，知道遍历到最大下标位置出，开启一个新的序列遍历
"""

from collections import Counter

# 32 ms 47.61% ｜ 13.2 MB 13.84%
def partition_labels_v1(S):
	# 统计每个字符出现的次数
	char_count_dict = dict(Counter(S))

	# 存放最终结果序列的数组
	sequences = list()
	# 临时存放序列的数组
	temp_seq = list()
	# 存放当前序列中出现的各元素
	temp_seq_chars = set()

	for char in S:
		temp_seq_chars.add(char)
		temp_seq.append(char)
		char_count_dict[char] -= 1
		# 是否终止当前序列
		flag = True
		for c in temp_seq_chars:
			if char_count_dict[c] != 0:
				flag = False

		# 如果终止序列，则对临时遍历赋值
		if flag:
			sequences.append(temp_seq)
			temp_seq = list()
			temp_seq_chars = set()
	result = list(map(len, sequences))
	return result


# 36ms %32.05 | 12.9 86.96%
def partition_labels_v2(S):
	# 得到每个字符的start、end元素位置
	char_loc_dict = dict()
	for i in range(len(S)):
		char_loc_dict.setdefault(S[i], [i, i])
		if S[i] in char_loc_dict:
			char_loc_dict[S[i]][1] = i

	# 存放最终结果序列的数组
	sequences = list()

	start = 0
	end = 0
	for j in range(len(S)):
		if char_loc_dict[S[j]][1] > end:
			end = char_loc_dict[S[j]][1]
		if j == end:
			sequences.append([start, end])
			start = end + 1
			end = end + 1
	result = list(map(lambda k: k[1] - k[0] + 1, sequences))
	return result


S = "ababcbacadefegdehijhklij"
result = partition_labels_v2(S)
print(result)

